#include "quickSort.h"
#include "insertSort.h"

void Swap(ElementType *a, ElementType *b)
{
    ElementType Tmp;
    Tmp = *a;
    *a = *b;
    *b = Tmp;
}

//三数中值分割法
ElementType Median3(ElementType A[], int left, int right)
{
    int center = (left + right) / 2;
    if (A[left] > A[center])
    {
        Swap(&A[left], &A[center]);
    }
    if (A[center] > A[right])
    {
        Swap(&A[center], &A[right]);
    }
    if (A[left] > A[center])
    {
        Swap(&A[left], &A[center]);
    }
    Swap(&A[center], &A[right - 1]);
    return A[right - 1];
}

static void Qsort(ElementType A[], int left, int right)
{
    int i, j;
    ElementType tmp;
    if (left + Cutoff < right)
    {
        tmp = Median3(A, left, right);
        i = left, j = right - 1;
        for (;;)
        {
            while (A[++i] < tmp)
                ;

            while (A[--j] > tmp)
                ;

            //当i和j相交叉时归类结束
            //数组两侧通过三数中值分割填补符合条件的数值，这样当ij交叉时，两者都是合法地址
            if (i < j)
            {
                Swap(&A[i], &A[j]);
            }
            else
            {
                break;
            }
        }
        Swap(&A[i], &A[right - 1]);
        Qsort(A, left, i - 1);
        Qsort(A, i + 1, right);
    }
    else
    {
        //当数组足够小时，使用插入排序更有效率
        InsertionSort(A + left, right - left + 1);
    }
}

void QuickSort(ElementType A[], int N)
{
    Qsort(A, 0, N - 1);
}